Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 4
з дисципліни «Програмування складних алгоритмів»
Тема «Методи пошуку у масивах»
Варіант № 24
Дата «5» травня 2022
Мета роботи: Метою лабораторної роботи є отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних .
Завдання до роботи
Методичні вказівки
Лабораторна робота спирається на знання й уміння, отримані при вивченні наступних питань лекції:
– Пошук – знаходження будь-якої конкретної інформації у великому обсязі раніше зібраних даних. Дані діляться на записи, і кожний запис має хоча б один ключ. Ключ використовується для того, щоб відрізнити один запис від іншого. Метою пошуку є знаходження всіх записів, що підходять до заданого ключа пошуку.
– Пошук елементу в масиві (послідовний пошук – неупорядкованої інформації, але також можна використовувати його й на відсортованих даних)
– Двійковий пошук (Бінарний пошук)
– Пошук послідовності елементів в масиві.
– Алгоритм Рабіна-Карпа
Завдання до лабораторної роботи:
1. Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром.
2. Знайти заданий елемент у впорядкованому масиві згідно варіантів за таким принципом
Завдання
/
1.2. Теоретичні відомості
Задача пошуку елемента в послідовності - одна з важливих задач програмування як з теоретичної, так і практичної точок зору. Ось її формулювання:
Нехай A = {a1, a2, ...} - послідовність однотипних елементів і b - деякий елемент, який володіє властивістю P. Знайти місце елемента b в послідовності А. Оскільки представлення послідовності в пам’яті може бути здійснено в виді масиву, задачі можуть бути уточнені як задачі пошуку елемента в масиві A:
Знайти максимальний елемент масиву;
Знайти даний елемент масиву;
Знайти k-тий за величиною елемент масиву;
Основні алгоритми пошуку елементів в масиві:
Лінійний пошук
Ідея : Проглядати почергово елементи масиву, доки не буде знайдено шуканий елемент або не убде досягнуто кінець масиву.
Код ф-ції:
//Передаємо масив, ключ, розмір масиву
int linSearch(int arr[], int Key, int arrSize){
for (int i = 0; i < arrSize; i++){ //Шукаємо елемент
if (arr[i] == requiredKey)
return i; //Якщо знайшли
}
return -1; //Якщо елемент не знайшли
}
Лінійний пошук з бар'єром
Ідея : Як і у попередньому випадку, алементи проглядаються по черзі, але для зменшення кількості порівнянь після останнього елемента додається елемент з ключем, що дорівнює шуканому значенню.
Код ф-ції:
//Передаємо масив, ключ, розмір масиву
int find(int *arr, int size, int key) {
int last = arr[size - 1]; //Зберігаємо останій елемент масива
arr[size - 1] = key;//Гарантуємо , що значення є в масиві
int i = 0;
for (i = 0; arr[i] != value; ++i) {//Шукаємо індекс елемента
}
arr[size - 1] = last;//Відновлюємо останій елемент
if (i != (size - 1) || value == last) {//Не дійшли до бар'єра або останій елемент був шуканим
return i; //Знайшли елемент
}else{
return -1; //Не знайшли елемент
}
}
Бінарний пошук
Ідея : Пошук реалізується в упорядкованому масиві. Шукане значення слід порівняти з ключем середнього елементу, у результаті цього порівняння визначити, у якій половині масиву знаходиться шуканий ключ, і знову застосувати ту саму процедуру до половини масиву. Процес припиняється, коли буде знайдено елемент, або коли "довжина" таблиці стане менше 1.
Код ф-ції:
//Передаємо масив, ліву та праву границ, ключ
int Search_Binary (int arr[], int left, int right, int key){
int midd = 0;
while (1){
midd = (left + right) / 2; // Середній елемент
if (key < arr[midd]) //Якщо ключ менше середьного значення
right = midd - 1; // зменшуєм праву границю
else if (key > arr[midd]) //Якщо ключ більше середь...
